﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>
#include <ctype.h>
#include<stdbool.h>
#include<stddef.h>//NULL
#include<time.h>
//int** fun(int n) 
//{
//    int** s = (int**)malloc(n * sizeof(int*));
//    while (n--)
//        s[n] = (int*)malloc(n * sizeof(int));
//    return s;
//}
//struct ListNode 
//{
//	int val;
//	struct ListNode* next;
//};
//int kthToLast(struct ListNode* head, int k) 
//{
//	struct ListNode* p = head;
//	int n = 0;
//	while (p)
//	{
//		n++;
//		p = p->next;
//	}
//	n = n - k;
//	while (n--)
//	{
//		head = head->next;
//	}
//	return head->val;
//}
//#define _CRT_SECURE_NO_WARNINGS 1
//#include <stdio.h>
//#include <string.h>
//#include <math.h>
//#include <stdlib.h>
//#include <assert.h>
//#include <ctype.h>
//#include<stdbool.h>
//typedef int LTDataType;
//typedef struct ListNode
//{
//	LTDataType data;
//	struct ListNode* next;//存储下一个结点的地址
//	struct ListNode* prev;//存储上一个结点的地址
//}LTNode;
////申请新结点
//LTNode* buyNode(LTDataType x)
//{
//	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
//	node->data = x;
//	//双向链表指针初始的时候要指向本身
//	node->next = node->prev = node;
//	return node;
//}
////初始化
//LTNode* LTInit()
//{
//	LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
//	phead->next = phead->prev = phead;
//	//初始时头结点两个指针都应该指向自己
//	phead->data = 0;
//	return phead;
//}
////尾插
//void LTPushBack(LTNode* phead, LTDataType x)
//{
//	LTNode* newnode = buyNode(x);
//	//我们应当先改的是新插入的结点，这样才会使之后改变原链表的指向不是非常麻烦
//	newnode->prev = phead->prev;
//	newnode->next = phead;
//	newnode->prev->next = newnode;
//	//也可以改为
//	//phead->prev->next = newnode;
//	//都表示原来的尾结点的next指针指向
//	phead->prev = newnode;
//}
////打印
//void LTPrint(LTNode* phead)
//{
//	LTNode* pcur = phead->next;
//	//结束条件就是到首结点
//	while (pcur != phead)
//	{
//		printf("%d -> ", pcur->data);
//		//如果是其他数据就可以改
//		pcur = pcur->next;
//		//如果要逆向打印也可以把next全部替换成prev
//	}
//}
////头插
//void LTPushFront(LTNode* phead, LTDataType x)
//{
//	assert(phead);
//	//不能传入空指针
//	LTNode* newnode = buyNode(x);
//	newnode->next = phead->next;
//	newnode->prev = phead;
//	phead->next->prev = newnode;
//	//或者这样写
//	//newnode->next->prev=newnode;
//	phead->next = newnode;
//}
////检查是否链表有数据
//bool LTEmpty(LTNode* phead)
//{
//	assert(phead);
//	return phead->next == phead;
//}
////尾删
//void LTPopBack(LTNode* phead)
//{
//	assert(!LTEmpty(phead));
//	LTNode* del = phead->prev;
//	del->prev->next = phead;
//	phead->prev = del->prev;
//	free(del);
//	del = NULL;
//}
//void test()
//{
//	LTNode* plist = LTInit();
//	LTPushBack(plist, 1);
//	LTPushBack(plist, 2);
//	LTPushBack(plist, 3);
//	LTPushBack(plist, 4);
//	LTPushFront(plist, 2);
//	LTPushFront(plist, 4);
//	LTPushFront(plist, 6);
//	LTPushFront(plist, 8);
//	LTPrint(plist);
//	LTPopBack(plist);
//	printf("\n");
//	LTPrint(plist);
//	LTPopBack(plist);
//	printf("\n");
//	LTPrint(plist);
//	LTPopBack(plist);
//	printf("\n");
//	LTPrint(plist);
//	LTPopBack(plist);
//	printf("\n");
//	LTPrint(plist);
//}
////头删
//void LTPopFront(LTNode* phead)
//{
//	assert(!LTEmpty(phead));
//	LTNode* del = phead->next;
//	del->next->prev = phead;
//	phead->next = del->next;
//	free(del);
//	del = NULL;
//}
//void test1()
//{
//	LTNode* plist = LTInit();
//	LTPushBack(plist, 1);
//	LTPushBack(plist, 2);
//	LTPushBack(plist, 3);
//	LTPushBack(plist, 4);
//	LTPushFront(plist, 2);
//	LTPushFront(plist, 4);
//	LTPushFront(plist, 6);
//	LTPushFront(plist, 8);
//	LTPrint(plist);
//	LTPopFront(plist);
//	printf("\n");
//	LTPrint(plist);
//	LTPopFront(plist);
//	printf("\n");
//	LTPrint(plist);
//	LTPopFront(plist);
//	printf("\n");
//	LTPrint(plist);
//}
////查找
//LTNode* LTFind(LTNode* phead, LTDataType x)
//{
//	LTNode* pcur = phead->next;
//	while (pcur != phead)
//	{
//		if (pcur->data == x)
//		{
//			return pcur;
//		}
//		pcur = pcur->next;
//	}
//	return NULL;
//}
////在pos位置之后插入数据
//void LTInsert(LTNode* pos, LTDataType x)
//{
//	assert(pos);
//	LTNode* newnode = buyNode(x);
//	newnode->next = pos->next;
//	newnode->prev = pos;
//	newnode->next->prev = newnode;
//	pos->next = newnode;
//}
////把pos位置数据删除
//void LTErase(LTNode* pos)
//{
//	assert(pos);
//	pos->prev->next = pos->next;
//	pos->next->prev = pos->prev;
//	free(pos);
//	pos = NULL;
//}
//void test2()
//{
//	LTNode* plist = LTInit();
//	LTPushBack(plist, 1);
//	LTPushBack(plist, 2);
//	LTPushBack(plist, 3);
//	LTPushBack(plist, 4);
//	LTPushFront(plist, 2);
//	LTPushFront(plist, 4);
//	LTPushFront(plist, 6);
//	LTPushFront(plist, 8);
//	LTNode* find = LTFind(plist, 2);
//	LTInsert(find, 3);
//	LTPrint(plist);
//	printf("\n");
//	LTErase(find);
//	LTPrint(plist);
//}
////销毁链表
//void LTDesTroy(LTNode** pphead)
//{
//	LTNode* pcur = (*pphead)->next;
//	while (pcur != *pphead)
//	{
//		LTNode* next = pcur->next;
//		free(pcur);
//		pcur = next;
//		//不能置为空
//	}
//	free(*pphead);
//	*pphead = NULL;
//}
//void test3()
//{
//	LTNode* plist = LTInit();
//	LTPushBack(plist, 1);
//	LTPushBack(plist, 2);
//	LTDesTroy(plist);
//}
//int main()
//{
//	test3();
//	return 0;
//}
//#define _CRT_SECURE_NO_WARNINGS 1
//#include <stdio.h>
//#include <string.h>
//#include <math.h>
//#include <stdlib.h>
//#include <assert.h>
//#include <ctype.h>
//#include<stdbool.h>
//#include<stddef.h>//NULL
//
////堆的结构
////能存储的数据有很多种
//
//typedef int HPDataType;
//typedef struct Heap
//{
//	HPDataType* arr;
//	int size;//有效数据的个数
//	int capacity;//容量
//}HP;
////堆的初始化
//void HPInit(HP* php)
//{
//	assert(php);
//	php->arr = NULL;
//	php->size = php->capacity = 0;
//}
////堆的销毁
//void HPDesTory(HP* php)
//{
//	//判断是否为NULL
//	if (php->arr)
//	{
//		free(php->arr);
//	}
//	php->arr = NULL;
//	php->size = php->capacity = 0;
//}
////交换函数
//void Swap(HPDataType* x, HPDataType* y)
//{
//	HPDataType tmp = *x;
//	*x = *y;
//	*y = tmp;
//}
//////向上调整算法
////void AdjustUp(HPDataType* arr, int child)
////{
////    HPDataType parent = (child - 1) / 2;
////    while (child > 0)
////    {
////        if (arr[child] < arr[parent])
////        {
////            Swap(&arr[child], &arr[parent]);
////            //或者可以加个continue,之后把else去掉，只留break；
////            child = parent;
////            parent = (child - 1) / 2;
////        }
////        else
////        {
////            break;
////        }
////    }
////}
////向上调整算法
//void AdjustUp(HPDataType* arr, int child)
//{
//	HPDataType parent = (child - 1) / 2;
//	while (child > 0)
//	{
//		if (arr[child] > arr[parent])
//		{
//			Swap(&arr[child], &arr[parent]);
//			//或者可以加个continue,之后把else去掉，只留break；
//			child = parent;
//			parent = (child - 1) / 2;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
////插入数据
//void HPPush(HP* php, HPDataType x)
//{
//	assert(php);
//	if (php->size == php->capacity)
//	{
//		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
//		//增容
//		HPDataType* tmp = (HPDataType*)realloc(php->arr, sizeof(HPDataType) * (newcapacity));
//		//增容失败
//		if (tmp == NULL)
//		{
//			perror("realloc fail!\n");
//			exit(1);
//		}
//		php->arr = tmp;
//		php->capacity = newcapacity;
//	}
//	php->arr[php->size] = x;
//	//第二个传的参数是php->size，因为下标这个时候最大已经是size,有size+1个数据，我们还没有执行++的操作
//	AdjustUp(php->arr, php->size);
//	++php->size;
//}
////判空
//bool HPEmpty(HP* php)
//{
//	assert(php);
//	return php->size == 0;
//}
////向下调整算法
//void AdjustDown(HPDataType* arr, int parent, int n)
//{
//	int child = parent * 2 + 1;
//	while (child < n)
//	{
//		//先找最小的
//		if (child + 1 < n && arr[child] > arr[child + 1])
//		{
//			child++;
//		}
//		if (arr[parent] > arr[child])
//		{
//			Swap(&arr[child], &arr[parent]);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
//////向下调整算法建堆
////void HeapSort(HPDataType* arr, int n)
////{
////    for (int i = (n - 2) / 2; i >= 0; i--)
////    {
////        AdjustDown(arr, i, n);
////    }
////    //堆排序
////    int end = n - 1;
////    while (end > 0)
////    {
////        Swap(&arr[0], &arr[end]);
////        AdjustDown(arr, 0, end);
////        end--;
////    }
////}
////删除栈顶数据
//void HPpop(HP* php)
//{
//	assert(!HPEmpty(php));
//	Swap(&php->arr[0], &php->arr[php->size - 1]);
//	--php->size;
//	AdjustDown(php->arr, 0, php->size);
//}
////取堆顶元素
//HPDataType HPTop(HP* php)
//{
//	assert(!HPEmpty(php));
//	return php->arr[0];
//}
////测试函数
//void test()
//{
//	HP hp;
//	HPInit(&hp);
//	HPPush(&hp, 4);
//	HPPush(&hp, 6);
//	HPPush(&hp, 8);
//	HPPush(&hp, 10);
//	for (int i = 0; i < 4; i++)
//	{
//		printf("%d ", hp.arr[i]);
//	}
//	while (!HPEmpty(&hp))
//	{
//		printf("%d ", HPTop(&hp));
//		HPpop(&hp);
//	}
//	HPDesTory(&hp);
//}
////向下调整算法建堆
//void HeapSort(HPDataType* arr, int n)
//{
//	for (int i = (n - 2) / 2; i >= 0; i--)
//	{
//		AdjustDown(arr, i, n);
//	}
//	//堆排序
//	int end = n - 1;
//	while (end > 0)
//	{
//		Swap(&arr[0], &arr[end]);
//		AdjustDown(arr, 0, end);
//		end--;
//	}
//}
////向上调整算法建堆
//void HeapSort01(HPDataType* arr, int n)
//{
//	for (int i = 0; i < n; i++)
//	{
//		AdjustUp(arr, i);
//	}
//	//堆排序
//	int end = n - 1;
//	while (end > 0)
//	{
//		Swap(&arr[0], &arr[end]);
//		AdjustDown(arr, 0, end);
//		end--;
//	}
//}
////int main()
////{
////    //test();
////    int arr[] = { 17,20,10,13,19,15 };
////    int n = sizeof(arr) / sizeof(arr[0]);
////    HeapSort01(arr, n);
////    for (int i = 0; i < n; i++)
////    {
////        printf("%d ", arr[i]);
////    }
////    return 0;
////}
////向下调整算法
////void AdjustDown(HPDataType* arr, int parent, int n)
////{
////    int child = parent * 2 + 1;
////    while (child < n)
////    {
////        //先找最小的
////        if (child + 1 < n && arr[child] > arr[child + 1])
////        {
////            child++;
////        }
////        if (arr[parent] > arr[child])
////        {
////            Swap(&arr[child], &arr[parent]);
////            parent = child;
////            child = parent * 2 + 1;
////        }
////        else
////        {
////            break;
////        }
////    }
////}
//void CreateNDate()
//{
//	//造数据
//	long n = 100000;
//	//生成随机数
//	srand(time(0));
//	const char* file = "data.txt";
//	FILE* fin = fopen(file, "w");
//	if (fin == NULL)
//	{
//		perror("fopen error!\n");
//		return;
//	}
//	for (long i = 0; i < n; i++)
//	{
//		long x = (rand() + i) % 1000000;
//		fprintf(fin, "%d\n", x);
//	}
//	fclose(fin);
//}
//void TopK()
//{
//	int k = 0;
//	printf("请输入K: ");
//	scanf("%d", &k);
//	//读取文件前K个数据建堆
//	const char* file = "data.txt";
//	FILE* fout = fopen(file, "r");
//	if (fout == NULL)
//	{
//		perror("fopen error!\n");
//		exit(1);
//	}
//	//找最大的前K个数，建小堆
//	int* minHeap = (int*)malloc(sizeof(int) * k);
//	if (minHeap == NULL)
//	{
//		perror("malloc fail!\n");
//		exit(2);
//	}
//	//读取文件前K个数据建堆
//	for (int i = 0; i < k; i++)
//	{
//		fscanf(fout, "%d", &minHeap[i]);
//	}
//	//建堆
//	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
//	{
//		AdjustDown(minHeap, i, k);
//	}
//	//变量剩下的n-k个数据，进行调整入堆
//	long x;
//	while (fscanf(fout, "%d", &x) != EOF)
//	{
//		if (x > minHeap[0])
//		{
//			minHeap[0] = x;
//		}
//		AdjustDown(minHeap, 0, k);
//	}
//	for (int i = 0; i < k; i++)
//	{
//		printf("%d ", minHeap[i]);
//	}
//	fclose(fout);
//	free(minHeap);
//	minHeap = NULL;
//}
//int main()
//{
//	CreateNDate();
//	TopK();
//	return 0;
//}
struct TreeNode 
{
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};
typedef struct TreeNode TreeNode;
//求二叉树结点个数
int TreeSize(TreeNode* root)
{
    if (root == NULL)
    {
        return 0;
    }
    return 1 + TreeSize(root->left) + TreeSize(root->right);
}
//前序遍历
void PreOrder(TreeNode* root, int* arr, int* pi)
{
    if (root == NULL)
    {
        return;
    }
    arr[(*pi)++] = root->val;
    PreOrder(root->left, arr, pi);
    PreOrder(root->right, arr, pi);
}
int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    //我们需要自己求出结点个数
    *returnSize = TreeSize(root);
    int* arr = (int*)malloc(sizeof(int) * (*returnSize));
    int i = 0;
    //我们需要不断递增下标，所以要传址操作
    PreOrder(root, arr, &i);
    return arr;
}
//中序遍历
void zhongOrder(TreeNode* root, int* arr, int* pi)
{
    if (root == NULL)
    {
        return;
    }
    zhongOrder(root->left, arr, pi);
    arr[(*pi)++] = root->val;
    zhongOrder(root->right, arr, pi);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
    //我们需要自己求出结点个数
    *returnSize = TreeSize(root);
    int* arr = (int*)malloc(sizeof(int) * (*returnSize));
    int i = 0;
    //我们需要不断递增下标，所以要传址操作
    zhongOrder(root, arr, &i);
    return arr;
}
//后序遍历
void houOrder(TreeNode* root, int* arr, int* pi)
{
    if (root == NULL)
    {
        return;
    }
    houOrder(root->left, arr, pi);
    houOrder(root->right, arr, pi);
    arr[(*pi)++] = root->val;
}
int* postorderTraversal(struct TreeNode* root, int* returnSize) 
{
    //我们需要自己求出结点个数
    *returnSize = TreeSize(root);
    int* arr = (int*)malloc(sizeof(int) * (*returnSize));
    int i = 0;
    //我们需要不断递增下标，所以要传址操作
    houOrder(root, arr, &i);
    return arr;
}